class TISP

Definition

Let $S,T : \mathbb{N} \to \mathbb{N}$ be constructible functions. A language $L \subseteq \{0,1\}^*$ is in the complexity class $\mathbf{TISP}(T(n),S(n))$ if there exists a TM $M$ deciding $L$ in time $T(n)$ and space $S(n)$.

Notes

• $\mathbf{TISP}(T(n),S(n)) \neq \mathbf{DTIME}(T(n)) \cap \mathbf{SPACE}(S(n))$ (see DTIME and SPACE)

References

1. https://archive.model.in.tum.de/um/courses/complexity/SS11/slides/lecture11.pdf slide 6